package com.kevinkk.dp;

/**
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 * 假设每一种面额的硬币有无限个。
 *
 * 如果求组合数就是 外层for 循环遍历物品， 内层for遍历背包‼️
 * 如果求排列数就是 外层for 遍历背包， 内层for循环遍历物品‼️
 */

/**
 * 完全背包，并且是求 方法数
 * 完全背包：先遍历物品、再遍历背包（顺序可颠倒），并且是顺序遍历背包
 *          dp 公式是累加的
 */

public class CoinChangeII {
    class Solution {
        public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int i = 0; i < coins.length; i++) {
                for (int j = coins[i]; j <= amount; j++) {
                    dp[j] += dp[j - coins[i]];
                }
            }

            return dp[amount];
        }
    }
}
